// InfixToPostfix.java
import java.util.*;

public class InfixToPostfix {

    private String infix;
    private String postfix;
    private final Map<Character, Integer> isp;  // 运算符的栈内优先级
    private final Map<Character, Integer> icp;  // 运算符的栈外优先级

    public InfixToPostfix(String infixExpression) {
        this.infix = infixExpression;
        this.postfix = "";
        this.isp = new HashMap<>();
        this.icp = new HashMap<>();

        // 运算符的栈内优先级
        isp.put('+', 3);
        isp.put('|', 5);
        isp.put('*', 7);
        isp.put('(', 1);
        isp.put(')', 8);
        isp.put('#', 0);

        // 运算符的栈外优先级
        icp.put('+', 2);
        icp.put('|', 4);
        icp.put('*', 6);
        icp.put('(', 8);
        icp.put(')', 1);
        icp.put('#', 0);
    }

    // 判断一个字符是否为字母
    public boolean isLetter(char check) {
        return (check >= 'a' && check <= 'z') || (check >= 'A' && check <= 'Z');
    }

    // 获取栈内优先级
    public int ispFunc(char c) {
        int priority = isp.getOrDefault(c, -1);
        if (priority == -1) {
            System.err.println("错误：出现未知符号！");
            System.exit(1);
        }
        return priority;
    }

    // 获取栈外优先级
    public int icpFunc(char c) {
        int priority = icp.getOrDefault(c, -1);
        if (priority == -1) {
            System.err.println("错误：出现未知符号！");
            System.exit(1);
        }
        return priority;
    }

    // 中缀转后缀的转换过程
    public void infToPost() {
        String infixWithHash = infix + "#";
        Stack<Character> stack = new Stack<>();
        int loc = 0;

        while (!stack.isEmpty() || loc < infixWithHash.length()) {
            if (isLetter(infixWithHash.charAt(loc))) {
                postfix += infixWithHash.charAt(loc);
                loc++;
            } else {
                char c1 = stack.isEmpty() ? '#' : stack.peek();
                char c2 = infixWithHash.charAt(loc);
                if (ispFunc(c1) < icpFunc(c2)) {
                    stack.push(c2);
                    loc++;
                } else if (ispFunc(c1) > icpFunc(c2)) {
                    postfix += c1;
                    stack.pop();
                } else {
                    if (c1 == '#' && c2 == '#') break;
                    stack.pop();
                    loc++;
                }
            }
        }
    }

    // 获取后缀表达式
    public String getResult() {
        postfix = ""; // 清空结果
        infToPost();
        return postfix;
    }
}
